struct point {
	double x,y,z;
	static double eps;
	static double inf;
	point() {
		x=y=z=0;
	}
	point(double _x,double _y,double _z):x(_x),y(_y),z(_z){};
};
double point::eps=1e-10;
double point::inf=1e10;
point INF(2*point::inf,2*point::inf,2*point::inf);
//line: point a point b
//plane: point a normal vector b
point operator+(const point &a,const point &b) {
	return point(a.x+b.x,a.y+b.y,a.z+b.z);
}
point operator-(const point &a,const point &b) {
	return point(a.x-b.x,a.y-b.y,a.z-b.z);
}
double operator*(const point &a,const point &b) {
	return a.x*b.x+a.y*b.y+a.z*b.z;
}
point operator *(const point &a,double f) {
	return point(a.x*f,a.y*f,a.z*f);
}
point operator *(double f,const point &a) {
	return point(a.x*f,a.y*f,a.z*f);
}
point& operator +=(point &a,const point &b) {
	a.x+=b.x,a.y+=b.y,a.z+=b.z;
	return a;
}
point& operator -=(point &a,const point &b) {
	a.x-=b.x,a.y-=b.y,a.z-=b.z;
	return a;
}
point& operator *=(point &a,const double f) {
	a.x*=f,a.y*=f,a.z*=f;
	return a;
}
point cross(const point &a,const point &b) {
	return point(a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x);
}
double length(const point &a) {
	return sqrt(a.x*a.x+a.y*a.y+a.z*a.z);
}
int sign(double f) {
	if (f>point::eps) return 1;
	if (f<-point::eps) return -1;
	else return 0;
}
point rotate(const point &a,double rad) { //2-D rotation counter-clockwise
	return point(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad),a.z);
}
point getfoot(const point &p,const point &a,const point &b) { //get perpendicular foot
	point c=b-a;
	return a+c*(c*(p-a)/(c*c));
}
double distptol(const point &p,const point &a,const point &b) { //distance from p to a-b
	return length(p-getfoot(p,a,b));
}
double disptosge(const point &p,const point &a,const point &b) {
	point c=getfoot(p,a,b);
	if ((c-a)*(c-b)<0) return length(p-c);
	if ((c-a)*(b-a)<0) return length(p-a);
	else return length(p-b);
}
bool segcross(point a,point b,point c,point d,int mode) { //0:strict 1:loose 2-d
	int t1=sign(cross(b-a,c-a).z);
	int t2=sign(cross(b-a,d-a).z);
	if (t1*t2==1) return false;
	int t3=sign(cross(d-c,a-c).z);
	int t4=sign(cross(d-c,b-c).z);
	if (t3*t4==1) return false;
	if (t1==0 && t2==0 && t3==0 && t4==0) {
		if (mode==1) return false;
		double x1=min(a.x,b.x),x2=max(a.x,b.x);
		double y1=min(a.y,b.y),y2=max(a.y,b.y);
		double x3=min(c.x,d.x),x4=max(c.x,d.x);
		double y3=min(c.y,d.y),y4=max(c.y,d.y);
		if (sign(min(x2,x4)-max(x1,x3))>=0 && sign(min(y2,y4)-max(y1,y3))>=0) return true;
		else return false;
	}
	return true;
}
point getinterseg(point a,point b,point c,point d) {
	point p1=b-a,p2=d-c;
	double f1=cross(a,b).z,f2=cross(c,d).z;
	double f3=cross(p1,p2).z;
	return point((f2*p1.x-f1*p2.x)/f3,(f2*p1.y-f1*p2.y)/f3,0);
}
double distptopla(const point &p,const point &a,const point &n) { // distance point p to plane (a,n)
	return fabs((p-a)*n/length(n));
}
point getfoot3(const point &p,const point &a,const point &n) { //get perpendicular foot 3D
	double len=(p-a)*n/length(n);
	return p-len*n;
}
point getintersegpla(const point &a,const point &b,const point &p,const point &n) {//intersection line to plane
	if (sign((b-a)*n)==0) return INF;
	double t=(n*(p-a))/(n*(b-a));
	if (t>=0 && t<=1) return a+t*(b-a);
	else return INF;
}
point getinterlinepla(const point &a,const point &b,const point &p,const point &n) {//intersection line to plane
	if (sign((b-a)*n)==0) return INF;
	double t=(n*(p-a))/(n*(b-a));
	return a+t*(b-a);
}
double volume(const point &a,const point &b,const point &c,const point &d) {
	return (d-a)*cross(b-a,c-a);
}
pair<point,point> getinterplapla(const point &p1,const point &n1,const point &p2,const point &n2) {
	if (sign(n1*n2)==0) return make_pair(INF,INF);
	point s; s.x=n1.y-n1.z; s.y=-n1.x+n1.z; s.z=n1.x-n1.y;
	s+=p1; point s1=getinterlinepla(p1,s,p2,n2);
	return make_pair(s1,s1+cross(n1,n2));
}
bool getinterline3(const point &p1,const point &u,const point &p2,const point &v,double &s) {
//get intersection p1+u*s p2+v*t return false if parallel/coincide else return s denote the intersection or foot
	double b=u*u*(v*v)-u*v*(u*v);
	if (sign(b)==0) return false;
	double t=u*v*(v*(p1-p2))-v*v*(u*(p1-p2));
	s=t/b;
	return true;
}
struct circle {
	point c;
	double r;
	circle(point _c,double _r):c(_c),r(_r) {}
	circle() {
		c.x=c.y=c.z=r=0;
	}
	point get(double rad) const{
		return c+point(cos(rad),sin(rad),0)*r;
	}
};
int getinterlinecir(point p1,point p2,const circle &C,double &t1,double &t2,vector<point> &sol) {
//return 0 if not intersect return 1 if tangent return 2 if intersect
//t1 t2 denotes angle sol denotes points
	p2-=p1;
	double a=p2.x,b=p1.x-C.c.x,c=p2.y,d=p1.y-C.c.y;
	double e=a*a+c*c,f=2*(a*b+c*d),g=b*b+d*d-C.r*C.r;
	double delta=f*f-4*e*g;
	if (sign(delta)<0) return 0;
	if (sign(delta)==0) {
		t1=t2=-f/(2*e); sol.push_back(p1+p2*t1);
		return 1;
	}
	t1=(-f-sqrt(delta))/(2*e); sol.push_back(p1+p2*t1);
	t2=(-f+sqrt(delta))/(2*e); sol.push_back(p1+p2*t2);
	return 2;
}
int getintercircir(const circle &c1,const circle &c2,vector<point> &sol) {
//return -1 if coincide return 0 if not intersect return 1/2 intersect points
	double d=length(c1.c-c2.c);
	if (sign(d)==0) {
		if (sign(c1.r-c2.r)==0) return -1;
		else return 0;
	}
	if (sign(c1.r+c2.r-d)<0) return 0;
	if (sign(d-fabs(c1.r-c2.r))<0) return 0;
	double a=atan2(c2.c.y-c1.c.y,c2.c.x-c1.c.x);
	double da=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
	point p1=c1.get(a-da),p2=c1.get(a+da);
	sol.push_back(p1);
	if (sign(length(p1-p2))==0) return 1;
	sol.push_back(p2);
	return 2;
}
